/*
** $Id: ltable.c,v 2.118 2016/11/07 12:38:35 roberto Exp $
** Lua tables (hash)
** See Copyright Notice in lua.h
*/

#define ltable_c
#define LUA_CORE

#include "lprefix.h"


/*
** Implementation of tables (aka arrays, objects, or hash tables).
** Tables keep its elements in two parts: an array part and a hash part.
** Non-negative integer keys are all candidates to be kept in the array
** part. The actual size of the array is the largest 'n' such that
** more than half the slots between 1 and n are in use.
** Hash uses a mix of chained scatter table with Brent's variation.
** A main invariant of these tables is that, if an element is not
** in its main position (i.e. the 'original' position that its hash gives
** to it), then the colliding element is in its own main position.
** Hence even when the load factor reaches 100%, performance remains good.
*/

#include <math.h>
#include <limits.h>

#include "lua.h"

#include "ldebug.h"
#include "ldo.h"
#include "lgc.h"
#include "lmem.h"
#include "lobject.h"
#include "lstate.h"
#include "lstring.h"
#include "ltable.h"
#include "lvm.h"


/*
** Maximum size of array part (MAXASIZE) is 2^MAXABITS. MAXABITS is
** the largest integer such that MAXASIZE fits in an unsigned int.
*/
#define MAXABITS    cast_int(sizeof(int) * CHAR_BIT - 1)
#define MAXASIZE    (1u << MAXABITS)

/*
** Maximum size of hash part is 2^MAXHBITS. MAXHBITS is the largest
** integer such that 2^MAXHBITS fits in a signed int. (Note that the
** maximum number of elements in a table, 2^MAXABITS + 2^MAXHBITS, still
** fits comfortably in an unsigned int.)
*/
#define MAXHBITS    (MAXABITS - 1)


#define hashpow2(t,n)       (gnode(t, lmod((n), sizenode(t))))

#define hashstr(t,str)      hashpow2(t, (str)->hash)
#define hashboolean(t,p)    hashpow2(t, p)
#define hashint(t,i)        hashpow2(t, i)


/*
** for some types, it is better to avoid modulus by power of 2, as
** they tend to have many 2 factors.
*/
#define hashmod(t,n)    (gnode(t, ((n) % ((sizenode(t)-1)|1))))


#define hashpointer(t,p)    hashmod(t, point2uint(p))


#define dummynode       (&dummynode_)

static const Node dummynode_ = {
    {NILCONSTANT},  /* value */
    {
        {NILCONSTANT, 0}
    }  /* key */
};


/*
** Hash for floating-point numbers.
** The main computation should be just
**     n = frexp(n, &i); return (n * INT_MAX) + i
** but there are some numerical subtleties.
** In a two-complement representation, INT_MAX does not has an exact
** representation as a float, but INT_MIN does; because the absolute
** value of 'frexp' is smaller than 1 (unless 'n' is inf/NaN), the
** absolute value of the product 'frexp * -INT_MIN' is smaller or equal
** to INT_MAX. Next, the use of 'unsigned int' avoids overflows when
** adding 'i'; the use of '~u' (instead of '-u') avoids problems with
** INT_MIN.
*/
#if !defined(l_hashfloat)
static int l_hashfloat( lua_Number n ) {
    int i;
    lua_Integer ni;
    n = l_mathop( frexp )( n, &i ) * -cast_num( INT_MIN );

    if ( !lua_numbertointeger( n, &ni ) ) { /* is 'n' inf/-inf/NaN? */
        lua_assert( luai_numisnan( n ) ||
                    l_mathop( fabs )( n ) == cast_num( HUGE_VAL ) );
        return 0;
    }
    else {   /* normal case */
        unsigned int u = cast( unsigned int, i ) + cast( unsigned int, ni );
        return cast_int( u <= cast( unsigned int, INT_MAX ) ? u : ~u );
    }
}
#endif


/*
** returns the 'main' position of an element in a table (that is, the index
** of its hash value)
*/
static Node* mainposition( const Table* t, const TValue* key ) {
    switch ( ttype( key ) ) {
    case LUA_TNUMINT:
        return hashint( t, ivalue( key ) );

    case LUA_TNUMFLT:
        return hashmod( t, l_hashfloat( fltvalue( key ) ) );

    case LUA_TSHRSTR:
        return hashstr( t, tsvalue( key ) );

    case LUA_TLNGSTR:
        return hashpow2( t, luaS_hashlongstr( tsvalue( key ) ) );

    case LUA_TBOOLEAN:
        return hashboolean( t, bvalue( key ) );

    case LUA_TLIGHTUSERDATA:
        return hashpointer( t, pvalue( key ) );

    case LUA_TLCF:
        return hashpointer( t, fvalue( key ) );

    default:
        lua_assert( !ttisdeadkey( key ) );
        return hashpointer( t, gcvalue( key ) );
    }
}


/*
** returns the index for 'key' if 'key' is an appropriate key to live in
** the array part of the table, 0 otherwise.
*/
static unsigned int arrayindex( const TValue* key ) {
    if ( ttisinteger( key ) ) {
        lua_Integer k = ivalue( key );

        if ( 0 < k && ( lua_Unsigned )k <= MAXASIZE ) {
            return cast( unsigned int, k );    /* 'key' is an appropriate array index */
        }
    }

    return 0;  /* 'key' did not match some condition */
}


/*
** returns the index of a 'key' for table traversals. First goes all
** elements in the array part, then elements in the hash part. The
** beginning of a traversal is signaled by 0.
*/
static unsigned int findindex( lua_State* L, Table* t, StkId key ) {
    unsigned int i;

    if ( ttisnil( key ) ) {
        return 0;    /* first iteration */
    }

    i = arrayindex( key );

    if ( i != 0 && i <= t->sizearray ) { /* is 'key' inside array part? */
        return i;    /* yes; that's the index */
    }
    else {
        int nx;
        Node* n = mainposition( t, key );

        for ( ;; ) { /* check whether 'key' is somewhere in the chain */
            /* key may be dead already, but it is ok to use it in 'next' */
            if ( luaV_rawequalobj( gkey( n ), key ) ||
                    ( ttisdeadkey( gkey( n ) ) && iscollectable( key ) &&
                      deadvalue( gkey( n ) ) == gcvalue( key ) ) ) {
                i = cast_int( n - gnode( t, 0 ) ); /* key index in hash table */
                /* hash elements are numbered after array ones */
                return ( i + 1 ) + t->sizearray;
            }

            nx = gnext( n );

            if ( nx == 0 ) {
                luaG_runerror( L, "invalid key to 'next'" );    /* key not found */
            }
            else {
                n += nx;
            }
        }
    }
}


int luaH_next( lua_State* L, Table* t, StkId key ) {
    unsigned int i = findindex( L, t, key ); /* find original element */

    for ( ; i < t->sizearray; i++ ) { /* try first array part */
        if ( !ttisnil( &t->array[i] ) ) { /* a non-nil value? */
            setivalue( key, i + 1 );
            setobj2s( L, key + 1, &t->array[i] );
            return 1;
        }
    }

    for ( i -= t->sizearray; cast_int( i ) < sizenode( t ); i++ ) { /* hash part */
        if ( !ttisnil( gval( gnode( t, i ) ) ) ) { /* a non-nil value? */
            setobj2s( L, key, gkey( gnode( t, i ) ) );
            setobj2s( L, key + 1, gval( gnode( t, i ) ) );
            return 1;
        }
    }

    return 0;  /* no more elements */
}


/*
** {=============================================================
** Rehash
** ==============================================================
*/

/*
** Compute the optimal size for the array part of table 't'. 'nums' is a
** "count array" where 'nums[i]' is the number of integers in the table
** between 2^(i - 1) + 1 and 2^i. 'pna' enters with the total number of
** integer keys in the table and leaves with the number of keys that
** will go to the array part; return the optimal size.
*/
static unsigned int computesizes( unsigned int nums[], unsigned int* pna ) {
    int i;
    unsigned int twotoi;  /* 2^i (candidate for optimal size) */
    unsigned int a = 0;  /* number of elements smaller than 2^i */
    unsigned int na = 0;  /* number of elements to go to array part */
    unsigned int optimal = 0;  /* optimal size for array part */

    /* loop while keys can fill more than half of total size */
    for ( i = 0, twotoi = 1; *pna > twotoi / 2; i++, twotoi *= 2 ) {
        if ( nums[i] > 0 ) {
            a += nums[i];

            if ( a > twotoi / 2 ) { /* more than half elements present? */
                optimal = twotoi;  /* optimal size (till now) */
                na = a;  /* all elements up to 'optimal' will go to array part */
            }
        }
    }

    lua_assert( ( optimal == 0 || optimal / 2 < na ) && na <= optimal );
    *pna = na;
    return optimal;
}


static int countint( const TValue* key, unsigned int* nums ) {
    unsigned int k = arrayindex( key );

    if ( k != 0 ) { /* is 'key' an appropriate array index? */
        nums[luaO_ceillog2( k )]++; /* count as such */
        return 1;
    }
    else {
        return 0;
    }
}


/*
** Count keys in array part of table 't': Fill 'nums[i]' with
** number of keys that will go into corresponding slice and return
** total number of non-nil keys.
*/
static unsigned int numusearray( const Table* t, unsigned int* nums ) {
    int lg;
    unsigned int ttlg;  /* 2^lg */
    unsigned int ause = 0;  /* summation of 'nums' */
    unsigned int i = 1;  /* count to traverse all array keys */

    /* traverse each slice */
    for ( lg = 0, ttlg = 1; lg <= MAXABITS; lg++, ttlg *= 2 ) {
        unsigned int lc = 0;  /* counter */
        unsigned int lim = ttlg;

        if ( lim > t->sizearray ) {
            lim = t->sizearray;  /* adjust upper limit */

            if ( i > lim ) {
                break;    /* no more elements to count */
            }
        }

        /* count elements in range (2^(lg - 1), 2^lg] */
        for ( ; i <= lim; i++ ) {
            if ( !ttisnil( &t->array[i - 1] ) ) {
                lc++;
            }
        }

        nums[lg] += lc;
        ause += lc;
    }

    return ause;
}


static int numusehash( const Table* t, unsigned int* nums, unsigned int* pna ) {
    int totaluse = 0;  /* total number of elements */
    int ause = 0;  /* elements added to 'nums' (can go to array part) */
    int i = sizenode( t );

    while ( i-- ) {
        Node* n = &t->node[i];

        if ( !ttisnil( gval( n ) ) ) {
            ause += countint( gkey( n ), nums );
            totaluse++;
        }
    }

    *pna += ause;
    return totaluse;
}


static void setarrayvector( lua_State* L, Table* t, unsigned int size ) {
    unsigned int i;
    luaM_reallocvector( L, t->array, t->sizearray, size, TValue );

    for ( i = t->sizearray; i < size; i++ ) {
        setnilvalue( &t->array[i] );
    }

    t->sizearray = size;
}


static void setnodevector( lua_State* L, Table* t, unsigned int size ) {
    if ( size == 0 ) { /* no elements to hash part? */
        t->node = cast( Node*, dummynode ); /* use common 'dummynode' */
        t->lsizenode = 0;
        t->lastfree = NULL;  /* signal that it is using dummy node */
    }
    else {
        int i;
        int lsize = luaO_ceillog2( size );

        if ( lsize > MAXHBITS ) {
            luaG_runerror( L, "table overflow" );
        }

        size = twoto( lsize );
        t->node = luaM_newvector( L, size, Node );

        for ( i = 0; i < ( int )size; i++ ) {
            Node* n = gnode( t, i );
            gnext( n ) = 0;
            setnilvalue( wgkey( n ) );
            setnilvalue( gval( n ) );
        }

        t->lsizenode = cast_byte( lsize );
        t->lastfree = gnode( t, size ); /* all positions are free */
    }
}


void luaH_resize( lua_State* L, Table* t, unsigned int nasize,
                  unsigned int nhsize ) {
    unsigned int i;
    int j;
    unsigned int oldasize = t->sizearray;
    int oldhsize = allocsizenode( t );
    Node* nold = t->node;  /* save old hash ... */

    if ( nasize > oldasize ) { /* array part must grow? */
        setarrayvector( L, t, nasize );
    }

    /* create new hash part with appropriate size */
    setnodevector( L, t, nhsize );

    if ( nasize < oldasize ) { /* array part must shrink? */
        t->sizearray = nasize;

        /* re-insert elements from vanishing slice */
        for ( i = nasize; i < oldasize; i++ ) {
            if ( !ttisnil( &t->array[i] ) ) {
                luaH_setint( L, t, i + 1, &t->array[i] );
            }
        }

        /* shrink array */
        luaM_reallocvector( L, t->array, oldasize, nasize, TValue );
    }

    /* re-insert elements from hash part */
    for ( j = oldhsize - 1; j >= 0; j-- ) {
        Node* old = nold + j;

        if ( !ttisnil( gval( old ) ) ) {
            /* doesn't need barrier/invalidate cache, as entry was
               already present in the table */
            setobjt2t( L, luaH_set( L, t, gkey( old ) ), gval( old ) );
        }
    }

    if ( oldhsize > 0 ) { /* not the dummy node? */
        luaM_freearray( L, nold, cast( size_t, oldhsize ) );    /* free old hash */
    }
}


void luaH_resizearray( lua_State* L, Table* t, unsigned int nasize ) {
    int nsize = allocsizenode( t );
    luaH_resize( L, t, nasize, nsize );
}

/*
** nums[i] = number of keys 'k' where 2^(i - 1) < k <= 2^i
*/
static void rehash( lua_State* L, Table* t, const TValue* ek ) {
    unsigned int asize;  /* optimal size for array part */
    unsigned int na;  /* number of keys in the array part */
    unsigned int nums[MAXABITS + 1];
    int i;
    int totaluse;

    for ( i = 0; i <= MAXABITS; i++ ) {
        nums[i] = 0;    /* reset counts */
    }

    na = numusearray( t, nums ); /* count keys in array part */
    totaluse = na;  /* all those keys are integer keys */
    totaluse += numusehash( t, nums, &na ); /* count keys in hash part */
    /* count extra key */
    na += countint( ek, nums );
    totaluse++;
    /* compute new size for array part */
    asize = computesizes( nums, &na );
    /* resize the table to new computed sizes */
    luaH_resize( L, t, asize, totaluse - na );
}



/*
** }=============================================================
*/


Table* luaH_new( lua_State* L ) {
    GCObject* o = luaC_newobj( L, LUA_TTABLE, sizeof( Table ) );
    Table* t = gco2t( o );
    t->metatable = NULL;
    t->flags = cast_byte( ~0 );
    t->array = NULL;
    t->sizearray = 0;
    setnodevector( L, t, 0 );
    return t;
}


void luaH_free( lua_State* L, Table* t ) {
    if ( !isdummy( t ) ) {
        luaM_freearray( L, t->node, cast( size_t, sizenode( t ) ) );
    }

    luaM_freearray( L, t->array, t->sizearray );
    luaM_free( L, t );
}


static Node* getfreepos( Table* t ) {
    if ( !isdummy( t ) ) {
        while ( t->lastfree > t->node ) {
            t->lastfree--;

            if ( ttisnil( gkey( t->lastfree ) ) ) {
                return t->lastfree;
            }
        }
    }

    return NULL;  /* could not find a free place */
}



/*
** inserts a new key into a hash table; first, check whether key's main
** position is free. If not, check whether colliding node is in its main
** position or not: if it is not, move colliding node to an empty place and
** put new key in its main position; otherwise (colliding node is in its main
** position), new key goes to an empty position.
*/
TValue* luaH_newkey( lua_State* L, Table* t, const TValue* key ) {
    Node* mp;
    TValue aux;

    if ( ttisnil( key ) ) {
        luaG_runerror( L, "table index is nil" );
    }
    else if ( ttisfloat( key ) ) {
        lua_Integer k;

        if ( luaV_tointeger( key, &k, 0 ) ) { /* does index fit in an integer? */
            setivalue( &aux, k );
            key = &aux;  /* insert it as an integer */
        }
        else if ( luai_numisnan( fltvalue( key ) ) ) {
            luaG_runerror( L, "table index is NaN" );
        }
    }

    mp = mainposition( t, key );

    if ( !ttisnil( gval( mp ) ) || isdummy( t ) ) { /* main position is taken? */
        Node* othern;
        Node* f = getfreepos( t ); /* get a free place */

        if ( f == NULL ) { /* cannot find a free place? */
            rehash( L, t, key ); /* grow table */
            /* whatever called 'newkey' takes care of TM cache */
            return luaH_set( L, t, key ); /* insert key into grown table */
        }

        lua_assert( !isdummy( t ) );
        othern = mainposition( t, gkey( mp ) );

        if ( othern != mp ) { /* is colliding node out of its main position? */
            /* yes; move colliding node into free position */
            while ( othern + gnext( othern ) != mp ) { /* find previous */
                othern += gnext( othern );
            }

            gnext( othern ) = cast_int( f - othern ); /* rechain to point to 'f' */
            *f = *mp;  /* copy colliding node into free pos. (mp->next also goes) */

            if ( gnext( mp ) != 0 ) {
                gnext( f ) += cast_int( mp - f ); /* correct 'next' */
                gnext( mp ) = 0; /* now 'mp' is free */
            }

            setnilvalue( gval( mp ) );
        }
        else {   /* colliding node is in its own main position */
            /* new node will go into free position */
            if ( gnext( mp ) != 0 ) {
                gnext( f ) = cast_int( ( mp + gnext( mp ) ) - f );    /* chain new position */
            }
            else {
                lua_assert( gnext( f ) == 0 );
            }

            gnext( mp ) = cast_int( f - mp );
            mp = f;
        }
    }

    setnodekey( L, &mp->i_key, key );
    luaC_barrierback( L, t, key );
    lua_assert( ttisnil( gval( mp ) ) );
    return gval( mp );
}


/*
** search function for integers
*/
const TValue* luaH_getint( Table* t, lua_Integer key ) {
    /* (1 <= key && key <= t->sizearray) */
    if ( l_castS2U( key ) - 1 < t->sizearray ) {
        return &t->array[key - 1];
    }
    else {
        Node* n = hashint( t, key );

        for ( ;; ) { /* check whether 'key' is somewhere in the chain */
            if ( ttisinteger( gkey( n ) ) && ivalue( gkey( n ) ) == key ) {
                return gval( n );    /* that's it */
            }
            else {
                int nx = gnext( n );

                if ( nx == 0 ) {
                    break;
                }

                n += nx;
            }
        }

        return luaO_nilobject;
    }
}


/*
** search function for short strings
*/
const TValue* luaH_getshortstr( Table* t, TString* key ) {
    Node* n = hashstr( t, key );
    lua_assert( key->tt == LUA_TSHRSTR );

    for ( ;; ) { /* check whether 'key' is somewhere in the chain */
        const TValue* k = gkey( n );

        if ( ttisshrstring( k ) && eqshrstr( tsvalue( k ), key ) ) {
            return gval( n );    /* that's it */
        }
        else {
            int nx = gnext( n );

            if ( nx == 0 ) {
                return luaO_nilobject;    /* not found */
            }

            n += nx;
        }
    }
}


/*
** "Generic" get version. (Not that generic: not valid for integers,
** which may be in array part, nor for floats with integral values.)
*/
static const TValue* getgeneric( Table* t, const TValue* key ) {
    Node* n = mainposition( t, key );

    for ( ;; ) { /* check whether 'key' is somewhere in the chain */
        if ( luaV_rawequalobj( gkey( n ), key ) ) {
            return gval( n );    /* that's it */
        }
        else {
            int nx = gnext( n );

            if ( nx == 0 ) {
                return luaO_nilobject;    /* not found */
            }

            n += nx;
        }
    }
}


const TValue* luaH_getstr( Table* t, TString* key ) {
    if ( key->tt == LUA_TSHRSTR ) {
        return luaH_getshortstr( t, key );
    }
    else {  /* for long strings, use generic case */
        TValue ko;
        setsvalue( cast( lua_State*, NULL ), &ko, key );
        return getgeneric( t, &ko );
    }
}


/*
** main search function
*/
const TValue* luaH_get( Table* t, const TValue* key ) {
    switch ( ttype( key ) ) {
    case LUA_TSHRSTR:
        return luaH_getshortstr( t, tsvalue( key ) );

    case LUA_TNUMINT:
        return luaH_getint( t, ivalue( key ) );

    case LUA_TNIL:
        return luaO_nilobject;

    case LUA_TNUMFLT: {
        lua_Integer k;

        if ( luaV_tointeger( key, &k, 0 ) ) { /* index is int? */
            return luaH_getint( t, k );    /* use specialized version */
        }

        /* else... */
        }  /* FALLTHROUGH */

    default:
        return getgeneric( t, key );
    }
}


/*
** beware: when using this function you probably need to check a GC
** barrier and invalidate the TM cache.
*/
TValue* luaH_set( lua_State* L, Table* t, const TValue* key ) {
    const TValue* p = luaH_get( t, key );

    if ( p != luaO_nilobject ) {
        return cast( TValue*, p );
    }
    else {
        return luaH_newkey( L, t, key );
    }
}


void luaH_setint( lua_State* L, Table* t, lua_Integer key, TValue* value ) {
    const TValue* p = luaH_getint( t, key );
    TValue* cell;

    if ( p != luaO_nilobject ) {
        cell = cast( TValue*, p );
    }
    else {
        TValue k;
        setivalue( &k, key );
        cell = luaH_newkey( L, t, &k );
    }

    setobj2t( L, cell, value );
}


static int unbound_search( Table* t, unsigned int j ) {
    unsigned int i = j;  /* i is zero or a present index */
    j++;

    /* find 'i' and 'j' such that i is present and j is not */
    while ( !ttisnil( luaH_getint( t, j ) ) ) {
        i = j;

        if ( j > cast( unsigned int, MAX_INT ) / 2 ) { /* overflow? */
            /* table was built with bad purposes: resort to linear search */
            i = 1;

            while ( !ttisnil( luaH_getint( t, i ) ) ) {
                i++;
            }

            return i - 1;
        }

        j *= 2;
    }

    /* now do a binary search between them */
    while ( j - i > 1 ) {
        unsigned int m = ( i + j ) / 2;

        if ( ttisnil( luaH_getint( t, m ) ) ) {
            j = m;
        }
        else {
            i = m;
        }
    }

    return i;
}


/*
** Try to find a boundary in table 't'. A 'boundary' is an integer index
** such that t[i] is non-nil and t[i+1] is nil (and 0 if t[1] is nil).
*/
int luaH_getn( Table* t ) {
    unsigned int j = t->sizearray;

    if ( j > 0 && ttisnil( &t->array[j - 1] ) ) {
        /* there is a boundary in the array part: (binary) search for it */
        unsigned int i = 0;

        while ( j - i > 1 ) {
            unsigned int m = ( i + j ) / 2;

            if ( ttisnil( &t->array[m - 1] ) ) {
                j = m;
            }
            else {
                i = m;
            }
        }

        return i;
    }
    /* else must find a boundary in hash part */
    else if ( isdummy( t ) ) { /* hash part is empty? */
        return j;    /* that is easy... */
    }
    else {
        return unbound_search( t, j );
    }
}



#if defined(LUA_DEBUG)

Node* luaH_mainposition( const Table* t, const TValue* key ) {
    return mainposition( t, key );
}

int luaH_isdummy( const Table* t ) {
    return isdummy( t );
}

#endif
